#pragma once
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <semaphore.h>
#include "memory.h"
#include "pregrow_memory.h"
#include "get_memory.h"
#include "release_memory.h"

extern int info[MAX_L];
extern int sum;
extern Buddy* p_tree;
extern void* base;
extern sem_t g_sem;

void *
pregrow_memory( void *p, int new_size )
{
    mem_header_t *pointer = (mem_header_t *)p;
    pointer = &pointer[-1];             // get the address of the header
    long unsigned int p_value = (long unsigned int) pointer;
	printf("Pregrow the memory block with header address: %p--------------------------\n", pointer);
    Buddy *node = (Buddy *)p_tree;
    Buddy *tree = (Buddy *)p_tree;
    Buddy *grow_node = NULL;

    int one = 1;
    int i, l;
    int old_size;
    int need = new_size + sizeof(mem_header_t);
    // find the tree node with manage info.
    int l0 = 0;
    int index = 0;           // for bit operation to index the node on a level

sem_wait(&g_sem);
    while (! grow_node) {
        if (p_value == (long unsigned int)node->p) {
            if (node->left ==NULL ) {
                if (node->right ==NULL) {
                    grow_node = node;
                    printf("found the node at level %d\n", l);
                }
                else {
                    printf("Invalid access!\n");
				    exit(1);            // right occurpied, misrelease
                }
            }
            else {

                node = node->left;
                l0++;
                index = index<<1;

                printf("look left to level %d\n", l);
            }
        }
        else if (node->right !=NULL ) {
            if (p_value >= (long unsigned int)(node->right->p)) {
                node = node->right;
                l0++;
                index = (index<<1) +1;
                printf("look right to level %d\n", l);
            }
            else { 
                node = node->left;
                l0++;
                index = index<<1;
            }
         }
            else {                  // right == NULL
                node = node->left;
                l0++;
                index = index<<1;
            }
       
    }

    // compute which level should the the goal block be on
    l = 0;          // to mark the level of suitable size.
    if (need > sum) {
sem_post(&g_sem);
        return NULL;}

    while (need <= sum/(one<<l)) {
        if (need <= sum/(one<<(l+1)))
            l++;
        else
            break;
    }

    // find the level difference
    int dif = l0 - l;

    // stay at same level to grow, or truncate
    if (dif <= 0) {
	    old_size = pointer->size;
        int size_dif = new_size - old_size;
        pointer->size = new_size;
		
        char *mv = (char *)p;
        if (size_dif > 0) {         // stay to grow
            for (i=0; i<old_size;i++) {
               mv[new_size-1 -i] = mv[old_size-1 -i];
            }
        }
        else if (size_dif < 0) {        // truncate from front
            for (i=0; i<new_size;i++) {
                mv[i] = mv[size_dif +i];
            }
        }
        else
            ;
		
sem_post(&g_sem);
        return p;
    }

    // stay to grow to higher level
    int stay = 1;       // represent if the memory can grow staying at original address
    int level_head = one<<l0;
    int ind = index;

    for (i=0; i<dif; i++) {
        if (ind%2 == 1 || tree[level_head + ind].p != NULL) {       // check if current is right node || next block is used [level_head-1+ index+1]
		    printf("Tree [%d] is already used\n", level_head + ind);
            stay = 0;
            break;
        }
        level_head = level_head/2;
        ind = ind/2;
    }

    if (stay) {
	    printf("OK to grow at original position\n");
        int tmp_l = l0;
        level_head = one<<l0;
        ind = index;
        for (i=0; i<=dif; i++) {         // destroy node from current level, till goal level
            tree[level_head -1 +ind].left = NULL;
            tree[level_head -1 +ind].right = NULL;
			
			printf("Destroy node %d by setting left and right null\n", level_head -1 +ind);   //why tree 3???? should be 

            if (i < dif)
                tree[level_head -1 +ind].p = NULL;      // the pointer in goal level not set to NULL

            info[tmp_l]++;
            tmp_l--;
            level_head = level_head/2;  
            ind = ind/2; 

        }
        // modify header info
        mem_header_t *tmp = tree[level_head -1 +ind].p;
        tmp->size = new_size;

        // do moving the contents
        old_size = pointer->size;
        int size_dif = new_size - old_size;
		
        char *mv = (char *)p;
        if (size_dif > 0) {         // stay to grow
            for (i=0; i<old_size;i++) {
               mv[new_size-1 -i] = mv[old_size-1 -i];
            }
        }
        else if (size_dif < 0) {        // truncate from front
            for (i=0; i<new_size;i++) {
                mv[i] = mv[size_dif +i];
            }
        }
        else
            ;		
sem_post(&g_sem);
        return (void *)&tmp[1];

    }
    else {

        // if the goal level has blocks available
        if (info[l] > 0) {
            void *result_p = get_memory(new_size);
            memcpy(result_p, p, new_size);
            release_memory(p);

            // move contents in the new block
            old_size = pointer->size;
            int size_dif = new_size - old_size;
		
            char *mv = (char *)result_p;
            if (size_dif > 0) {         // stay to grow
                for (i=0; i<old_size;i++) {
                    mv[new_size-1 -i] = mv[old_size-1 -i];
                }
            }
            else if (size_dif < 0) {        // truncate from front
                for (i=0; i<new_size;i++) {
                    mv[i] = mv[size_dif +i];
                }
            }
            else
                ;

sem_post(&g_sem);
            printf("The new address for the growed node: %p\n", result_p);
            return result_p;
        }
        else
		{
sem_post(&g_sem);
		    printf("Can't grow!\n");
            return NULL;	
		}
    }
        






}



